#!/usr/bin/python
# -*- coding:UTF-8 -*-
# @Time    : 2019/1/11 9:32
# @Author  : 王志鹏
# @Site    : 快速排序
# @File    : d1.py
# @Software: PyCharm
import time


def runTime(level=True):
    def wrapper(func):
        def inner_wrapper(*args, **kwargs):
            startTime = time.clock()  # 开始时间
            u = func(*args, **kwargs)
            endTime = time.clock()
            timeDifference = str(endTime - startTime)  # 时间差
            if level:
                print "%s方法执行完毕:用时%s秒" % (func.__name__, timeDifference[0:7])
            return u

        return inner_wrapper

    return wrapper


class Algorithm(object):
    def __init__(self):
        pass

    def QuickSort(self, myList, start, end):
        # 判断low是否小于high,如果为false,直接返回
        if start < end:
            i, j = start, end
            # 设置基准数
            base = myList[i]

            while i < j:
                # 如果列表后边的数,比基准数大或相等,则前移一位直到有比基准数小的数出现
                while (i < j) and (myList[j] >= base):
                    j = j - 1

                # 如找到,则把第j个元素赋值给第个元素i,此时表中i,j个元素相等
                myList[i] = myList[j]
                print myList, "后"
                # 同样的方式比较前半区
                while (i < j) and (myList[i] <= base):
                    i = i + 1
                print myList, "前"
                myList[j] = myList[i]
            # 做完第一轮比较之后,列表被分成了两个半区,并且i=j,需要将这个数设置回base
            myList[i] = base
            print myList, "结束"
            print
            # 递归前后半区
            self.QuickSort(myList, start, i - 1)
            self.QuickSort(myList, j + 1, end)
        return myList

    @runTime()
    def main(self):
        list = [5, 1, 2, 7, 9, 3, 4, 5, 10]
        print list
        print

        print self.QuickSort(list, 0, len(list) - 1)


if __name__ == '__main__':
    algorithm = Algorithm()
    algorithm.main()
